package 链表;

import javafx.beans.binding.When;
import jdk.nashorn.internal.ir.WhileNode;

import java.util.*;

public class Solution9 {
    //https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f
    //思路：栈
    public boolean isPail1 (ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            if(cur.val != stack.pop().val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
    //题解
    //思路1：list可以.size()获取链表节点个数与.get(i)获取指定位置的节点，下标从0开始的
    public boolean isPail2 (ListNode head) {
        List<Integer> nums = new ArrayList<>();//<>放的是整数包装，直接判断里面的值的
        while (head != null) {
            nums.add(head.val);
            head = head.next;
        }
        int i = 0;
        int j = nums.size() - 1;
        while(i < j) {
            if(!nums.get(i).equals(nums.get(j))) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    //思路2：快慢指针到中点然后翻转比较
    public boolean isPail3 (ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode head2 = reverse(slow);
        while (head2 != null) {
            if(head.val != head2.val) {
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}
